\chapter{常见并发问题}
\thispagestyle{empty}
这么多年来，许多研究者已经花了大量的时间和精力查找并发性bug。多数早期的工作聚焦在死锁上，这一主题已经在在前面的章节中涉及到了，但是本章会更深入一些[C+71]。最近的一些工作聚焦在研究其他类型常见的并发性bug。本章，我们通过真是的代码案例简略的了解一些并发性问题，以此来更好的理解需要注意哪些问题。因此，我们的问题是：

crux：如何处理常见的并发性问题
并发性bug往往出现在各种各样的常见模型中。编写健壮、正确的并发性代码的第一步是知道有哪些问题需要注意。


\section{存在哪些类型的bug}
首先，也是最明显的问题是：在复杂的并发编程中会出现哪些类型的并发bug呢？这个问题通常是很难回答的，但是已经有人为我们做了这个工作。具体来说，我们需要依赖与Lu等人的研究成果[L+08]，他非常详细地分析了许多流行的并发应用来弄清楚在实践中有哪些类型的bug会发生。

这个研究集中在四个主流且重要的开源软件：MySQL（一个流行的数据库管理系统），Apache（一个著名的web服务器），Mozilla（著名的网页浏览器）以及OpenOffice（一个免费版的MS Office套件）。在这个研究中，作者们调查了这些软件每个版本中所好找到的以及修复的并发bug，将开发者的工作做了量化分析；理解这个结果可以很好的理解有哪些类型的问题在成熟的代码中确实发生了。

表32.1\\

表32.1中展示了Lu和他的同事们对已研究问题的总结。从这个表中，你可以发现总共有105个bug，大部分不是死锁造成的（74个）；剩下的31个是死锁问题。进一步，你们可以看见每个软件的bug数；OpenOffice仅有8个并发性错误，而Mozilla有近60个。

现在我们稍稍深入到不同类型的bug（非死锁，死锁）。第一类非死锁bug，我们用一个例子来推进我们的讨论。第二类死锁bug，我们讨论一下那些已经完成的工作，包括阻止死锁、死锁避免和死锁处理。


\section{非死锁bug}
根据Lu的研究，非死锁bug多数是由并发bug造成的。但是，这些是什么类型的bug呢？它们什么会发生呢？怎么解决它们呢？现在，我们讨论由Lu等人发现的两种非死锁bug类型：违反原子性（atomicity violation）和违反执行顺序（order violation）。

\subsection{违反原子性bug}
首先，第一个问题是上面提到的违反原子性错误。这里有一个简单的例子，在MySQL中发现的。在阅读解释之前，可以尝试一下解决这个bug，试一下吧！
\begin{verbatim}
Thread 1::if (thd->proc_info) {...fputs(thd->proc_info, ...); 
...
Thread 2::thd->proc_info = NULL;
\end{verbatim}

在这个例子中，两个线程访问thd结构体中的成员proc\_info。第一个线程检测了该值是否为NULL并输出该值；第二个线程将其设置为NULL。很明显，如果第一个线程执行了检测但是接着在调用fputs之前被中断了，第二个线程可以在期间执行，因此将指针设为NULL；当第一个线程恢复执行是，由于fputs会解引用一个空指针，故它会崩溃。

根据Lu等人的观点，正式一点的违反原子性的定义是：『多次内存访问中违反了期望的串行序列』（比如，某一段代码期望是原子的，但是执行期并没有得到保证）。在上述的例子中，该段代码在检测proc\_info以及在fputs函数中使用proc\_info时，有一个原子性假设（atomicity assumption）（Lu的原话）；当假设被打破，这段代码就不会按照预期工作了。

要解决这种类型的问题通常都很直接（但并不总是这样子）。想到怎么解决上面的那个问题了么？

在这个解决方案中，我们简单地在使用共享变量的周围添加了锁，确保每个线程在访问proc\_info成员时，能够持有该锁。当然，任何其他访问该结构体的代码在执行该操作时也需要获取该锁。

\begin{verbatim}
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;Thread 1:: pthread_mutex_lock(&lock); if (thd->proc_info) {...fputs(thd->proc_info, ...); 
...pthread_mutex_unlock(&lock);Thread 2::pthread_mutex_lock(&lock);thd->proc_info = NULL;pthread_mutex_unlock(&lock);
\end{verbatim}

\subsection{违反执行顺序bug}
Lu等人发现的另一个常见的非死锁错误类型是：违反执行顺序。这里有一个简单的例子；同样的，看看你可不可以看出来下面的代码为什么有bug。
\begin{verbatim}
Thread 1::void init() {...mThread = PR_CreateThread(mMain, ...); 
...
}
Thread 2::void mMain(...) {    ...    mState = mThread->State;    ...}
\end{verbatim}
可能你已经发现，这段代码中线程2似乎假设了mThread变量已经被初始化了（即非NULL）；然而，如果线程1并没有先执行，那就没有那么幸运了，线程2就很可能会由于NULL指针而崩溃（假设mThread的值是初始为NULL；如果不是，由于线程2会通过该指针读取任意内存地址，甚至会有更奇怪的事情会发生）。

违反执行顺序的正式定义是：『两次内存访问的期望顺序被调换了（比如A必须总是在B之前执行，但是在执行期这个顺序未得到保证）』。[L+08]

解决这个问题通常是强制保证执行顺序。如我们之前详细讨论的，使用条件变量是一个简单且稳健的方法来添加序列化到现代代码中。因此，在上述的例子中，我们可以修改代码如下：
\begin{verbatim}
pthread_mutex_t mtLock = PTHREAD_MUTEX_INITIALIZER; 
pthread_cond_t mtCond = PTHREAD_COND_INITIALIZER; 
int mtInit = 0;
Thread 1::void init() {...mThread = PR_CreateThread(mMain, ...);// signal that the thread has been created... 
pthread_mutex_lock(&mtLock);mtInit = 1;pthread_cond_signal(&mtCond); 
pthread_mutex_unlock(&mtLock);... 
}
Thread 2::void mMain(...) {...// wait for the thread to be initialized... 
pthread_mutex_lock(&mtLock);while (mtInit == 0)pthread_cond_wait(&mtCond, &mtLock); 
pthread_mutex_unlock(&mtLock);mState = mThread->State;...
}
\end{verbatim}
在这段已经修复的代码中，我们已经添加了一个锁mtLock和对应的条件变量mtCond，以及一个状态变量mtInit。当初始化代码执行时，它将mtInit的状态设置为1并通知（其他线程）他已经完成了。如果线程2在此之前已经运行，它会等待此信号以及相应的状态变化，如果它在线程1之后执行，他们检测该状态并发现初始化工作已经完成（比如mtInit被设置为1），因此会正确的继续执行。注意，我们可以使用mThread作为状态变量，但是不要为了达到目的简单地这么做。当线程间的执行顺序很重要是，条件变量（或者信号量）可以解决这些问题。

\subsection{小结：非死锁bug}
Lu等人研究了97\%的非死锁错误，包括违反原子性和违反执行顺序。因此通过仔细的考虑这些类型的错误模型，编程者可以更好地避免这些问题。此外，越来越多的自动化死锁检测工具被开发出来，他们应该在开发中聚焦在这两种类型的错误上（它们占了非死锁错误的绝大部分）。

不幸地是，不是所有的错误都可以简单地像上面示例中那样被修复。有些需要更深入的理解程序是如何运行的，或者更大量的代码或数据结构调整需要解决。详见Lu等人的极好的论文。

\section{死锁bug}

除了上述的并发错误外，另一个典型的问题是：死锁，它在许多有着复杂锁协议的并发系统中都会发生。例如，当一个线程（线程1）持有了锁1并等待锁2；另一个线程（线程2）持有了锁2等待这锁1的释放，那么死锁就发生了。下面是阐述了这样一种潜在的死锁的代码片段：

代码片段表格\\

要注意，如果这段代码执行的话，死锁并不一定会发生；而是，可能会发生，比如，线程1获取了锁L1，然后发生上下文切换至线程2，此时线程2获取锁L2并试图获取L1。因此就会发生死锁，每个线程都在等待另一个线程并且都不能继续运行。详见图32.1；图中的环即表示死锁。

图32.1（死锁）\\

该图应当明确该问题，程序员应该如何用某种方法编写代码来解决死锁呢？

Crux：如何解决死锁
我们该如何构造系统来预防、避免或者至少检测并修复？这个问题在现今的系统中还是问题么？

\subsection{为什么会发生死锁}
也许你会想，如上面的展示的简单的死锁似乎可以很简单地避免。例如，如果线程1和线程2都确保以同样的顺序获取锁，那么死锁就不会发生了。那么死锁为什么会发生呢？

一个原因是，在大型项目中，组件之间会产生复杂的依赖关系。比如操作系统。虚拟内存系统可能为了从磁盘映射一块到内存页中，需要访问文件系统；问就爱你系统可能接着需要一页内粗来读取该块并因此依赖虚拟文件系统。因此，为大型系统中设计锁策略必须非常小心以避免循环依赖的死锁情况，这种情况可能会在代码中很自然地发生。

另一个原因是封装的本质。由于软件开发者被倡导要影藏实现的细节并因此是的软件能够更容易的以模块的方式构造起来。不幸的是，模块化并不能跟锁很好的相互契合。如Jula等人指出[J+08]，一些看似无害的接口正将你带向死锁。比如，Java的Vector类和AddAll()方法。该操作调用如下：
\begin{verbatim}
Vector v1, v2;
v1.AddAll(v2);
\end{verbatim}
在函数内部，由于该方法需要多线程安全，需要获取添加到每个vector（v1和v2）里的锁。上述操作以任意的顺序（比如先v1然后v2）获取上述的锁，然后将v2的内容添加到v1中。如果一些其他的线程几乎同时调用了v2.AddAll(v1)，那就有发生死锁的可能性了，所有的方式都被影藏在了被调用的应用里。

\subsection{产生死锁的条件}
要产生死锁，需要具备四个条件。[C+71]

\begin{itemize}
\item 互斥：线程对请求的资源声索排他的控制权（比如线程获取一个锁）。
\item 请求保持：线程在等待额外的资源时（比如想要获得的锁）保持对已分配资源的控制（比如已经获得的锁）。
\item 非抢占：资源（比如锁）不能被强行地从持有线程手中移除。
\item 循环等待：线程间存在一个循环链，使得每个线程持有一个或多个资源，而这些资源又是循环链中下一个线程所请求的资源。
\end{itemize}
如果这四个条件中的任何一个都不成立，那么死锁也就不会发生了。因此，我们首先来探究一下阻止死锁的技术；这里的每个策略都试图破坏上述中的一个条件，因此每个策略都是解决死锁为题的方法。

\subsection{死锁预防}

\subsubsection*{循环等待}
可能最切实可行的预防技术（无疑也是使用的最频繁的）是在编写锁相关代码时不引起循环等待。要做到这点，那就是在锁的获取操作上使其整体有序。比如，如果系统中仅有两个锁（L1和L2），要求获取锁L1总是在L2之前，就可以预防死锁。这种强制有序可以保证不会发生循环等待，因此就不会有死锁。

如你所想，这个方法需要非常仔细的设计全局的锁策略。另外，它仅仅只是个公约，任何一个马虎的程序员都可以很容易的忽略了锁协议并可能引发死锁。最后，它需要对代码有很深入的理解，以及调用的各式各样的程序；只要有一个失误就可能导致锁获取顺序的错误，从而导致死锁。

\subsubsection*{请求保持}
请求保持条件可以通过一次性获取所有的锁来避免。在实践中，可以通过如下方式实现：
\begin{verbatim}
lock(prevention);lock(L1);lock(L2);...unlock(prevention);
\end{verbatim}
通过先获取prevention锁来保证在锁获取之间不会有不合时宜的线程切换，从而死锁又可以被避免了。当然，它要求任何时候任何线程都要请求一个锁，即先获取全局锁prevention。例如，如果另一个线程试图以不同的顺序获取锁L1和L2，也是没有问题的，因为当它这么做时已经持有了锁prevention。

注意，这个方法有很多原因会使之变得很困难。如之前所说，封装又在跟我们作对：当调用一个函数时，这个方法需要我们确切地知道哪些锁是必须保持并提前获取。由于所有的锁都必须一次性获取，而不是真的需要时才获取，使得这个方法很可能会降低并发性。

\subsubsection*{非抢占}
我们通常将锁视为保持知道解锁函数被调用。多个锁的获取通常会给我们带来麻烦，因为在等待某一个锁时我们持有着另外一个锁。许多线程库提供了一组更加灵活的接口来避免这中情况。特别地，trylock()函数要么获取锁（如果未被获取）或者返回-1表示这个锁已经被占有了，如果想要获取这个锁的话那就稍后再来尝试。

这个接口可以用来构建一个无死锁、稳定有序的锁请求协议：
\begin{verbatim}
top:lock(L1);if (trylock(L2) == -1) {    unlock(L1);    goto top;
}
\end{verbatim}
要注意其他线程可以遵循同样的协议但是按照不同的顺序（先L2再L1）获取这些锁，但这个程序同样是无死锁的。然而，心得问题又产生了：活锁（livelock）。有可能（尽管可能性不大）两个线程会不停地尝试着这组代码并不停地获取锁失败。这种情况下，两个线程在一遍又一遍的执行这段代码（尽管这不是死锁），但是程序并没有往前进，因此我们称之为活锁。活锁问题也有解决方案：比如，其中一个线程可以在循环回去再来一遍之前添加一段随机延迟，从而降低竞争线程间的重复干扰的可能性。

关于这个方法的最后一点，它回避了使用trylock的方法中的困难部分。第一个问题由于封装的缘故仍然有可能发生：如果其中某个锁隐藏在了被调用的函数中，那么跳回起始点就会很难实现。如果线程同时获取了其他资源（L1除外），它必须确保小心的将之释放；比如，在获取了L1之后，线程又分配了一些内存，在请求L2失败后，在跳回顶部在此重新执行全部步骤前，需要将该内存释放。然而，在有限的情况下（比如上述的Java vector方法），这种方法是有效的。

\subsubsection*{互斥条件}
最后一个死锁预防技术就是避免产生互斥条件的可能。通常，我们知道这是比较困难的，因为要运行的代码确实需要有临界区。那我们可以做些什么呢？

Herlihy有个想法：可以设计各种各样的数据结构来实现无等待[H91]。思想很简单：通过强大的硬件指令，可以构造不需要显示锁的数据结构。

举个简单的例子，假设我们已经有了compare-and-swap指令，它是由硬件提供的一条原子指令，如下：
\begin{verbatim}
\end{verbatim}


设想，如果我们想要某个变量原子地增加一个特定值。我们可以如下图：
\begin{verbatim}
\end{verbatim}

不像之前，请求锁，执行更新操作，再释放锁，而是构造了一种方法：不停地使用compare-and-swap指令尝试将变量更新为新的值。这种方法，没有请求锁，也不会发生死锁（但是活锁仍然是可能的）。

我们来考虑一个稍微更复杂已点的例子：链表的插入。下面是在链表头部插入节点的代码：
\begin{verbatim}
\end{verbatim}

这段代码是很简单的插入操作，但是如果在多线程中『同时』调用，就会产生竞争条件（尝试自一下你能不能知道为什么）。当然，我们可以通过在代码上下添加锁的请求和释放来解决这个问题：
\begin{verbatim}
\end{verbatim}

在这个方法中，我们是按照传统的方法使用的锁。另外，我们尝试一下用compare-and-swap指令以无锁方法执行这个插入操作。下面是可能的方法：
\begin{verbatim}
\end{verbatim}
这段代码将下一个指针更新为当前的头节点，然后尝试将新创建的节点swap作为链表新的头结点。然而，如果其他线程成功的swap到了新的头结点，那么就会失败，会使得当前线程需要重新与新的头结点swap。

当然，要构造一个可用的链表不仅仅需要链表插入操作，不奇怪的是，链表的无锁插入，删除，查找等操作是很重要的。如果你觉得有兴趣的话，可以查阅丰富的资料来学习无锁同步。

\subsubsection*{死锁预防之调度}
与死锁预防不同，在有些场景中死锁避免会更好。避免需要有对在执行期各种各样的线程可能请求的锁有个全局的了解，以及接着以某种方式调度这些线程来保证不会有死锁发生。

举个例子，假设我们有两个处理器，四个线程，每个线程都在两个处理器上调度。假设知道线程1（T1）想获取锁L1和L2(在执行期的某点以某种顺序)，线程2（T2）也想获取L1和L2，线程3（T3）想获取L2，线程4（T4）不需要获取锁。我们可以将各个线程的锁请求列成如下的表：

锁请求表\\

一个智能的调度器会因此计算出只要T1和T2不同时运行即可，就不会发生死锁了。下图是一种调度方式：

时序图\\


注意到，T3和T1以及T3和T2有重叠是没问题的。即使T3想获取锁L2，那么与其他线程同时运行也不会导致死锁，因为它只想获取一个锁。

我们再来看一个例子。这个例子，对于同样的资源（还是锁L1和L2）有更多的竞争，如下表所示：

表\\

特别的，线程T1，T2和T3在它们执行期都想获取锁L1和L2。下图是可能的调度方案可以保证不会发生死锁。

时序图\\

你会发现，静态调度是一种保守的方法，会使得T1、T2和T3始终在同一个处理器上运行，因此任务的完成时间会被拉长。尽管使得这些任务并行执行是存在可能的，但是处于对死锁的考虑使得我们不能这么做，其代价就是牺牲性能。

一个著名的方法就是Dijkstra的银行家算法[D64]，在该文献中描述了很多类似的方法。不幸的是，这些方法只能在有限的环境中能够使用，比如，在知道要运行的全部任务和锁的嵌入式系统中。另外，这个方法只能实现有限的并行，正如上述第二个例子。因此通过调度来避免死锁不是一个可以广泛使用的通用解决方案。


TIP：不要总想着完美解决问题（TOM WEST定律）
Tom West，闻名于经典计算机工业书籍『Soul of a New Mahine』中的主题，说道：『不是所有值得做的事情都值得做到最好』，这是一个很好的工程师格言。如果某个坏事儿很少发生，无疑不应该花很大的努力以预防它，特别是坏事发生的代价很小时。

\subsubsection*{检测与恢复}
最后一个通常的策略是允许死锁的偶尔发生，然后在检测到死锁时采取一些措施解决。例如，如果操作系统一年死一次机，你只需要重启就又可以开心的继续工作了。如果死锁很少发生，这种无为而治的方式还是相当务实的。

许多数据库系统都引入了死锁检测和恢复技术。死锁检测器周期性的运行，构造一个资源图并检查是否有环。在存在环时，该系统需要重新启动。如果首先需要的是修复更加错综复杂的数据结构，那么人的介入会更轻松些。



\section{小结}
在这章中，我们学习了在并发编程汇总会发生的错误类型。第一，非死锁是非常常见的错误，但也通常更容易解决。包括：违反原子性和违反执行顺序，前者是应当一起执行的指令序列并没有一起执行，后者是线程的执行顺序并没有得到保证。

我们也简要的讨论了死锁：为什么会发生，可以做些什么解决它。这个问题如并发性一般古老，关于这个话题已经出了上百篇论文。在实践中最好的方法是小心，请求锁时保持有序，从而在第一次出现时就预防死锁的发生。无锁的方法还有些希望，可以在一些常用的库和关键的系统中看得到无锁数据结构的应用，包括Linux。然而，它们缺乏通用性，并且开发一套新的无锁数据结构的复杂度很大程度上限制了这种方法的应用。也许最好的解决方案是开发一套新的并发编程模型：比如MapReduce（来自Google）[GD02]，开发者可以在描述特定类型的并行计算时不需要任何锁。锁的问题是由其本质锁决定的，也许我们应当尽可能的避免使用锁，除非真的非用不可。





